Abbreviations found in the patent application are defined as follows:
AGWN additive white Gaussian noise
BER bit error rate
BLER block error rate
LDPC low-density parity-check
LDPCC low-density parity-check code
FEC forward error correction
IP internet protocol
TCP transport control protocol
TGn task group “n”
WLAN wireless local area network
When a transmitting end transmits data packets to a receiving end via a packet switched communication network, for instance via the Internet or an IP based wireless network, some of the data packets may be corrupted or lost on the way. It is therefore common practice to transmit in addition error correction data to the receiving end. The error correction data may enable the receiving end to restore corrupted or lost data to a considerable extent.
In order to minimize the amount of data which has to be transmitted, the error correction data may be transmitted, for example, only in case the receiving end does not acknowledge safe reception of a transmitted data packet. However, using an acknowledgement protocol is generally not feasible for point-to-multipoint transmissions. For ensuring a reliable transmission in a multicast transmission, conventionally a FEC scheme is implemented. Such a FEC scheme includes sending by default a certain amount of redundant data, which can assist a receiving end in reconstructing erroneous or missing data.
For producing the redundant data for a FEC scheme, various types of coding can be employed. The LDPC family is a class of FEC codes which result in encoded data that can be decoded efficiently using a message-passing algorithm over a graph. When used for erasure correction, the application of a message-passing algorithm is equivalent to solving a set of linear equations by recursive substitution. This type of decoding is also referred to as a chain reaction decoding.
A parity-check matrix which is associated to the employed code uniquely determines the decoding graph or the set of linear equations which have to be solved. The parity-check matrix of binary LDPC has been dealt with, for example, in the document: “Low Density Parity-Check Codes”, MIT Press, Cambridge, Mass., 1963, by R. G. Gallager, to which reference may be made.
There exist many types of LDPC codes that result in different decoding performances, depending on the dimensions of the LDPC parity-check matrix and the degree distribution of the associated graph. Some common codes include, for example, regular LDPCs, irregular LDPCs, Low Density Generator Matrix (LDGM) codes, Luby Transform (LT) codes and Raptor codes. Further, the dimensions of a LDPC parity-check matrix may be pre-determined or may be changed on the fly as new output symbols are generated, such as in the case of LT codes and Raptor codes. Two or more LDPC codes may also be cascaded for various reasons that include, but are not limited to, better decoding performance, lower complexity and ease of encoding.
In all cases, the receiving end must know the particular parity-check matrix of each constituent code for setting up the correct graph for message-passing decoding. The parity-check matrix has thus to be signaled to, or otherwise made known to, the receiving end. The LDPC codes are particularly efficient when they are adapted to encode large blocks of data. For example, the block length may typically be a few thousand data symbols. Accordingly, the number of elements in the parity-check matrix can become very large, typically a few million.
LDPC codes can have error correcting capabilities that rival the performance of “Turbo-Codes” and can be applicable over a wide range of statistical channels. In fact, some random irregular LDPC constructions based upon edge ensemble designs have error correcting capabilities measured in BER that are within 0.05 dB of the rate-distorted Shannon limit. Unfortunately, these LPDC code constructions often require long codeword constructions (on the order of 106 to 107 bits) in order to achieve these error rates. Despite good BER performance, these random code constructions often have poor BLER performances. Therefore, these random constructions typically do not lend themselves well to packet-based communication systems.
Another disadvantage of random constructions based on edge distribution ensembles is that, for each codeword length, a separate random construction is needed. Thus, communication systems employing variable block sizes (TCP/IP systems, for example) require multiple code definitions. Such multiple code definitions can consume a significant amount of non-volatile memory for large combinations of codeword lengths and code rates.
As an alternative to random LDPC constructions, structured LDPC constructions typically rely on a general algorithmic approach to constructing LDPC matrices which often requires much less non-volatile memory than random constructions. One such structured approach is based upon array codes. This approach can exhibit improved error performance (both BER and BLER performance) and a relatively low error floor for relatively high code rates (higher than 0.85).
The parity-check matrix H measures (N−K)×N, wherein N is number of elements in a codeword and K is the number of information elements in the codeword. The matrix H is also termed the LDPC mother code. For the specific example of a binary alphabet, N is the number of bits in the codeword and K is the number of information bits contained in the codeword for transmission over a wireless or a wired communication network or system. The number of information elements is therefore less than the number of codeword elements, so K<N. The coding rate R for a LDPC code is R=K/(N−P), wherein P is the number of punctured elements.